package 数据结构专栏.简单级别;

import java.util.*;

/**
 * @DESC 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 * @Author tzq
 * @Date 2020-04-14 20:43
 **/
public class _136_只出现一次的数字 {

    public static void main(String[] args) {
        int[] nums = new int[]{17, 12, 5, -6, 12, 4, 17, -5, 2, -3, 2, 4, 5, 16, -3, -4, 15, 15, -4, -5, -6};
        System.out.println(singleNumber(nums));


    }

    /**
     * 输入: [4,1,2,1,2]
     * 输出: 4
     * 用哈希表避免每次查找元素是否存在需要的 O(n)O(n) 时间。
     *
     * @param nums
     * @return
     */
    public static int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        for (int i : nums) {
            if (map.get(i) == 1) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 列表
     * <p>
     * 复杂度分析
     * <p>
     * 时间复杂度：O(n^2) 我们遍历 \text{nums}nums 花费 O(n)O(n) 的时间。我们还要在列表中遍历判断是否存在这个数字，花费 O(n)O(n) 的时间，所以总循环时间为 O(n^2)O(n
     * 空间复杂度：O(n)O(n) 。我们需要一个大小为 nn 的列表保存所有的 \text{nums}nums 中元素。
     *
     * @param nums
     * @return
     */
    public static int singleNumber2(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int i : nums) {
            if (!list.contains(i)) {
                list.add(i);
            } else {
                list.remove(list.size() - 1);
            }
        }

        return list.get(0);

    }


    /**
     * 最牛做法：异或运算
     *
     * 时间复杂度： O(n)O(n) 。我们只需要将 nums 中的元素遍历一遍，所以时间复杂度就是 nums 中的元素个数。
     * 空间复杂度：O(1)O(1) 。
     *
     * @param nums
     * @return
     */
    public int singleNumber3(int[] nums) {
        int a = 0;
        for (int i : nums) {
            a ^= i;
        }
        return a;
    }

}
